
class Solution {
    public:
        string path;
        vector<string> ret;
        int left = 0,right = 0 ,_n;
        vector<string> generateParenthesis(int n) {
            _n = n;
            dfs();
            return ret;
        }
        void dfs(){
            //cout<<path<<endl;
            if(left == _n && right ==_n){
                ret.push_back(path);
                return;
            }
            
            if(left < _n) {
                path.push_back('(');left++;
                dfs();
                path.pop_back();left--;
            }
            if(left > right){
                path.push_back(')');right++;
                dfs();
                path.pop_back();right--;
    
            }
        }
    };